class Solution:
    def re(self, x:int, y:int, m: int, n: int):
        if x > m or y > n:
            return 0
        
        if x == m and y == n:
            return 1
        
        return self.re(x+1, y, m, n) + self.re(x, y+1, m, n)
    
    def uniquePaths(self, m: int, n: int) -> int:
        return self.re(1,1, m, n)

if __name__ == '__main__':
    s = Solution()
    print(s.uniquePaths(3, 3))